#include <bits/stdc++.h>
using namespace std;

/*

*/

// 法一
class Solution {
public:
	using ll = long long;
	char kthCharacter(ll k, vector<int>& operations) {
		// 计算每一次操作后的字符串长度 长度超过k就停止
		vector<ll> lengths;
		ll curLen = 1;	// 初始化字符串"a" len = 1
		lengths.push_back(curLen);

		for (int op : operations) {
			if (curLen >= k) {
				// 长度超过 k 后续的操作不影响第k个字符位置
				lengths.push_back(curLen);
				continue;
			}

			// 操作数检测
			if (op == 0) {
				// 追加0: 追加自身 长度翻倍
				// 检查溢出
				if (curLen > LLONG_MAX / 2) 	curLen = LLONG_MAX;
				else 	curLen *= 2;
			} else {
				// 追加变换后的字符串 长度变为原来的两倍
				if (curLen > LLONG_MAX / 2)		curLen = LLONG_MAX;
				else 	curLen *= 2;
			}
			lengths.push_back(curLen);
		}

		// 逆向 推导第k个字符
		char curChar = 'a';
		// 最后一次操作开始逆向处理
		for (int i = operations.size() - 1; i >= 0; i--) {
			ll halfLen = lengths[i];		// 操作之前
			ll curTotalLen = lengths[i + 1];	// 操作之后
			if (k > halfLen) {
				// 第k个字符在操作后追加的部分
				k -= halfLen;	// 调整位置
				if (operations[i] == 1)		curChar = (curChar - 'a' + 1) % 26 + 'a';	// 计算变化后的字符
			}
		}
		return curChar;
	}
};

// 法二 
// 剪枝 
// 判断操作数那冗余了
class Solution {
public:
    using ll = long long;
    char kthCharacter(ll k, vector<int>& operations) {
        // 计算每次操作后的字符串长度，但长度超过k时停止计算
        vector<ll> lengths;
        ll currentLength = 1; // 初始字符串"a"的长度为1
        lengths.push_back(currentLength);

        for (int op : operations) {
            if (currentLength >= k) {
                // 长度已超过k，后续操作不影响第k个字符的位置
                lengths.push_back(currentLength);
                continue;
            }

            if (currentLength > LLONG_MAX / 2) {
                currentLength = LLONG_MAX; // 设为最大值，避免溢出
            } else {
                currentLength *= 2;
            }
            lengths.push_back(currentLength);
        }

        // 逆向推导第k个字符
        char currentChar = 'a'; // 初始字符为'a'

        // 从最后一次操作开始逆向处理
        for (int i = operations.size() - 1; i >= 0; i--) {
            ll halfLength = lengths[i];             // 操作前的字符串长度
            ll currentTotalLength = lengths[i + 1]; // 操作后的字符串长度

            if (k > halfLength) {
                // 第k个字符在操作后追加的部分
                k -= halfLength; // 调整k的位置

                if (operations[i] == 1) {
                    // 操作1会改变字符，需要计算变化后的字符
                    currentChar = (currentChar - 'a' + 1) % 26 + 'a';
                }
            }
            // 操作0不会改变字符，不需要额外处理
        }

        return currentChar;
    }
};

// 法三
class Solution {
public:
    // 计算无符号整数x的二进制表示中1的个数（汉明权重）
    int my_popcount(unsigned x) {
        int count = 0;
        while (x) {
            x &= x - 1; // 清除最低位的1
            count++;
        }
        return count;
    }

    // 计算无符号整数x的以2为底的对数（即最高位1的位置）
    int my_lg(unsigned x) {
        if (x == 0) return -1; // 未定义
        int pos = 0;
        while (x >>= 1) {
            pos++;
        }
        return pos;
    }

    // 主函数：找到执行完所有操作后的字符串中第k个字符
    char kthCharacter(long long k, vector<int>& operations) {
        long long ans = 0;    // 记录字符需要转换的次数
        long long t = 0, i = 0;
        
        // 逆向推导过程：将k逐步分解为2的幂之和
        while (k != 1) {
            // 计算k的最高位1的位置t，即满足2^t <= k的最大t
            t = __lg(k);
            
            // 特殊情况处理：如果k恰好是2的幂，需要减1以确保后续分解正确
            if (((long long)1 << t) == k) {
                t--;
            }
            
            // 将k减去2^t，继续分解剩余部分
            k = k - ((long long)1 << t);
            
            // 累加转换次数：如果operations[t]为1，则对应位置的字符需要转换
            if (operations[t]) {
                ans++;
            }
        }
        
        // 最终字符是'a'加上转换次数模26的结果，处理循环转换
        return 'a' + (ans % 26);
    }
};